package com.jiang.专题.动态规划.Q1035;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/01 22:13
 */
class Solution {
    // 二维动态规划
    // public int maxUncrossedLines(int[] nums1, int[] nums2) {
    //     int len1 = nums1.length;
    //     int len2 = nums2.length;
    //     int[][] dp = new int[len1 + 1][len2 + 1];
    //     for (int i = 1; i <= len1; i++) {
    //         for (int j = 1; j <= len2; j++) {
    //             if (nums1[i - 1] == nums2[j - 1]) {
    //                 dp[i][j] = dp[i - 1][j - 1] + 1;
    //             } else {
    //                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    //             }
    //         }
    //     }
    //     return dp[len1][len2];
    // }

    // 一维动态规划
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] dp = new int[len2 + 1];
        for (int i = 1; i <= len1; i++) {
            int temp = 0;
            for (int j = 1; j <= len2; j++) {
                int t = dp[j];
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = temp + 1;
                } else {
                    dp[j] = Math.max(dp[j - 1], dp[j]);
                }
                temp = t;
            }
        }
        return dp[len2];
    }
}
